Evolution of Three-Dimensional Cellular Automata: Genetic Algorithms

See One-Dimensional Cellular Automata for a basic introduction to cellular automata.

Introduction

Like their one and two-dimensional counterparts, three-dimensional cellular automata are specified by an initial state and a set of transition rules used to transform the state of each cell in each time step. The following presentation details the use of genetic algorithms to automatically generate the initial state and transition rules which arrive at a pre-specified goal state. Better understanding of cellular automata configuration could lead to developments in many diverse fields, from industrial design [Bentley and Corne, 2002] and nanotech computer architecture [Drexler, 1992] to morphology and embryology in biology [Thompson, 1942] [Stewart, 1998].

Goal State

Our three-dimensional cellular automata consists of a 40x40x40 cube of cells. In each time step the new value of a cell is computed based on the current value of the cell and the current values of its 26 direct neighbors. The system is initialized with some portion of the 27 cell cube centered at (21,21,21) turned on. The goal is to have the 27 cell cube centered at (31,31,31) be turned on (and all other cells off) 10 time steps later. The obvious (to us) solution is to initialize a cube at (21,21,21) and move it (+1,+1,+1) in each time step to arrive at (31,31,31) on time step 10.

StartEnd

While this particular problem is trivial, the solution search space is much too large for random search. A genetic algorithm that can solve this problem should also be able to solve problems in cellular automata configuration whose solutions are non-obvious to humans.

See also presentation on search.

Genotype

Each possible solution to the problem is represented as a 54-digit string, where each digit can take on 2, 3 or 5 values. The first 27 digits represent the initial state of the 27 cells of the cube centered at (21,21,21). The second 27 digits represent the transition rule applied to the cells. The transition rule forms an equation:

next_state[x][y][z] = transition_rule[0] * current_state[x][y][z-1] + transition_rule[1] * current_state[x-1][y][z-1] + transition_rule[2] * current_state[x+1][y][z-1] + ... + transition_rule[26] * current_state[x][y][z]; if(next_state < 0) next_state = 0; if(next_state > max) next_state = max

Three different cellular automata were tested:

Evaluation Function

Two different evaluation functions were used to score the generated solutions. Each applied a positive value for each "on" cell inside the target region and a negative value for each "on" cell outside the target region. Here "on" meant a value > 0, so no distinction was made between 2,3,4 [red,green,blue] in the three and five-valued automata.

The Genetic Algorithm

A population of 100 individuals was created with random values for each digit. The evaluation function was applied to determine the fitness of each individual. Pairs of individuals were randomly selected for reproduction. Their probability of selection was determined by their fitness. The selected individuals were both copied unchanged into the next generation and crossed over. The crossed over copies also each had a single random point mutation applied. In each generation the most fit individual was also preserved, guaranteeing the maximum fitness of the population could never fall.

Results

The genetic algorithm was run six times, applying both the old and new evaluation functions to the two, three, and five-valued automata. The results are graphed separately: Screen shots were also captured for generations 0,25,50,100,150,200,250 (skipping generations with unchanged fitness score) Of the six runs only one, the two-valued with new evaluation function run, reached the goal within 260 generations. This test was re-run using a different seed value for the random number generator. The configuration succeeded again, with nearly identical results. See the graph comparing the results: Of the rest of the results I would consider those for three-valued (both old and new eval) to be acceptable. And noting the larger search spaces, all runs may eventually reach the goal given sufficient generations / run time.

Conclusions

Genetic algorithms can be successfully applied to find useful cellular automata configurations within an enormous search space. Further investigation of the relationship between evaluation functions and numbers of allowed cell values is needed.

This work is continued using the Adaptive Culture Model in Evolution of Three-Dimensional Cellular Automata: Adaptive Culture Model.

Implementation Notes

Genetic algorithm and cellular automata custom implemented in C using gcc and OpenGL on Linux. Six simultaneous runs of 260 generations took 34 hours on a 700 MHz Athlon. Graphics by nvidia GeForce2, graphs by gnuplot, screen shots by the GIMP.

References

Bentley, Peter J. and David W. Corne, eds., 2002. Creative Evolutionary Systems.

Drexler, Eric K., 1992. Nanosystems: Molecular Machinery, Manufacturing, and Computation.

Stewart, Ian, 1998. Life's Other Secret: The New Mathematics of the Living World.

Thompson, D'Arcy Wentworth, 1942. On Growth and Form.